As consumer demand for high data rate applications, such as streaming video, expands, technology providers are forced to adopt new technologies to provide the necessary bandwidth. Multiple Input Multiple Output (“MIMO”) is an advanced radio system that employs multiple transmit antennas and multiple receive antennas to simultaneously transmit multiple parallel data streams. Relative to previous wireless technologies, MIMO enables substantial gains in both system capacity and transmission reliability without requiring an increase in frequency resources.
MIMO systems exploit differences in the paths between transmit and receive antennas to increase data throughput and diversity. As the number of transmit and receive antennas is increased, the capacity of a MIMO channel increases linearly, and the probability of all sub-channels between the transmitter and receiver fading simultaneously decreases exponentially. As might be expected, however, there is a price associated with realization of these benefits. Recovery of transmitted information in a MIMO system becomes increasingly complex with the addition of transmit antennas. In response this complexity, a variety of MIMO detection algorithms have been proposed.
Many MIMO detection algorithms, as well as many other communications applications, require finding a set of constellation symbols nearest a given input. This operation is called candidate generation. Candidate generation is employed in a variety of MIMO detectors, including the sphere detector, as described in Bernard M. Hochwald & Stephan ten Brink, Achieving Near-Capacity on a Multiple-Antenna Channel, 51 IEEE TRANSACTIONS ON COMMUNICATIONS 389 (2003), which requires ranking of candidates for each symbol. For pulse amplitude modulation (“PAM”) constellations, a simple candidate generation algorithm, as described in Mohamed Oussama Damen et al, On Maximum-Likelihood Detection and the Search for the Closest Lattice Point, 49 IEEE TRANSACTIONS ON INFORMATION THEORY 2389 (2003), is well-known. For other constellations, however, candidate generation is more difficult.
An ideal candidate generation algorithm computes the set of L symbols in a given alphabet that are nearest a given input in the Euclidean distance sense. Mathematically, the ideal candidate generator computes the set S(y,L):S(y,L)={x||y−x|<|y−aL|, xεA}, where aL is the L-th nearest symbol to y that belongs to the set A.
A brute-force implementation of the ideal candidate generation algorithm sorts all the elements of A by their distance from y, and then takes the first L elements of the sorted list. When the alphabet is large this is an inefficient implementation.